package com.Offer;

import com.pojo.TreeNode;

/*
    面试题26：树的子结构
    输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。（ps：我们约定空 树不是任意一个树的子结构）
 */
public class demo26 {
    public static void main(String[] args) {

    }

    public boolean hasSubTree(TreeNode source,TreeNode target){
        if(target == null){
            return true;
        }
        if(source == null){
            return false;
        }
        //在source的所有节点中找到了target的根节点后开始执行doesTreeHaveTree2
        if(doesTreeHaveTree2(source,target)){
            return true;
        }
        //递归寻找source的子节点中是否有target的根节点
        return hasSubTree(source.left,target) || hasSubTree(source.right,target);
    }


    public static boolean doesTreeHaveTree2(TreeNode source,TreeNode target){
        if(source == null && target == null){
            return true;
        }
        if(source == null || target == null){
            return false;
        }
        if(source.val != target.val){
            return false;
        }
        return doesTreeHaveTree2(source.left,target.left) && doesTreeHaveTree2(source.right,target.right);
    }
}
